package demo;

import java.util.stream.LongStream;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //统计数组中好三元组数目
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] let = new int[n];
        long[] nums = new long[n];
        for (int i = 0; i < nums2.length; i++) {
            let[nums2[i]] = i;
        }
        BitTree pre = new BitTree(n+1);
        for (int i = 0; i < n; i++) {
            int idx = let[nums1[i]] + 1;
            int search = pre.search(idx);
            nums[i] = search;
            pre.add(idx, 1);
        }
        BitTree back = new BitTree(n+1);
        for (int i = n-1; i >= 0; i--) {
            int idx = let[nums1[i]] + 1;
            int search = (n-1 - i) - back.search(idx);
            nums[i] *= search;
            back.add(idx, 1);
        }
        return LongStream.of(nums).sum();
    }
}
// 树状数组
class BitTree {
    private int[] bit;
    private int len;

    public BitTree(int len) {
        len = tableSizeFor(len) + 1;
        this.len = len;
        bit = new int[len];
    }

    public void add(int index, int k) {
        while (index < len) {
            bit[index] += k;
            index += lowBit(index);
        }
    }

    public int search(int index) {
        int m = 0;
        while (index > 0) {
            m += bit[index];
            index -= lowBit(index);
        }
        return m;
    }

    public int searchRange(int l, int r) {
        return search(r) - search(l-1);
    }

    // 得到x最后一位1和0构成的数字；如lowBit(1100) = (100);
    private int lowBit(int x) {
        return x & (~x + 1);
    }
    // HashMap原生方法，用于取2^n
    public int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 2 : n + 1;
    }
}
